package com.sfx.算法专题.动态规划.二维费用01背包;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-07-17
 * Time: 0:23
 */
public class Code_1_findMaxForm {
    static class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            //1.前.个字符串任意选,不超过i个0,j个1的最大子集长度为dp[i][j]
            int[][] dp = new int[m+1][n+1];
            //2.状态转移方程 :
            //dp[i][j] = dp[i-zeroNum][j-oneNum] + 1
            for(String str : strs) {
                int zeroNum = 0;
                int oneNum = 0;
                for(char c : str.toCharArray()) {
                    if(c == '0') zeroNum ++;
                    else oneNum ++;
                }
                for(int i =m;i>=zeroNum;--i) {
                    for(int j =n;j>=oneNum;--j) {
                        //                   不选         选择
                        dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    }
}